package com.yjz.leetcode.二叉树学习.二叉搜索树;

import java.util.Objects;

import static java.util.Objects.isNull;
import static java.util.Objects.nonNull;

/**
 * @author :yuanJinZhong
 * @description:二叉搜索树
 * @date :2018/11/24-15:12
 */
public class BstTree implements Tree {
  /**
   * 二叉搜索树的根节点
   */
  private Node root;

  @Override
  public Node find(Comparable data) {
    /**
     * 当前查询的节点,默认从根节点开始查询
     */
    Node current = root;
    /**
     *当前查询的节点不为null
     */
    while (nonNull(current)) {
      if (current.getData().compareTo(data) > 0) {
        current = current.getLeftChild();
      } else if (current.getData().compareTo(data) < 0) {
        current = current.getRightChild();
      } else {
        return current;
      }
    }
    return null;
  }

  @Override
  public boolean insert(Comparable data) {
    Node newNode = new Node<>(data);
    if (isNull(root)) {
      root = newNode;
      return true;
    } else {
      /**
       * 当前操作的节点,默认从根节点开始操作
       */
      Node current = root;
      /**
       * 《即将被插入的节点》的父节点
       */
      Node parentNode = null;
      while (nonNull(current)) {
        /**
         * 《即将被插入的节点》的父节点就是当前操作的节点(因为当前操作的节点可能是新节点的父节点)
         */
        parentNode = current;
        if (current.getData().compareTo(data) > 0) {
          current = current.getLeftChild();
          if (isNull(current)) {
            parentNode.setLeftChild(newNode);
            return true;
          }
        } else if (current.getData().compareTo(data) < 0) {
          current = current.getRightChild();
          if (isNull(current)) {
            parentNode.setRightChild(newNode);
            return true;
          }
        }
      }
    }
    return false;
  }

  @Override
  public void beforeOrderIteration(Node node) {
    if (nonNull(node)) {
      node.display();
      beforeOrderIteration(node.getLeftChild());
      beforeOrderIteration(node.getRightChild());
    }
  }

  @Override
  public void afterOrderIteration(Node node) {
    if (nonNull(node)) {
      afterOrderIteration(node.getLeftChild());
      afterOrderIteration(node.getRightChild());
      node.display();
    }
  }

  @Override
  public void middleOrderIteration(Node node) {
    if (nonNull(node)) {
      middleOrderIteration(node.getLeftChild());
      node.display();
      middleOrderIteration(node.getRightChild());
    }
  }
}
